package ahaArithmetic;

//Floyd_WarShall算法  计算任意的最短路径
public class Floyd_Warshall {

    static int map[][] = new int[][]{
            {1,2,2},
            {1,3,6},
            {1,4,4},
            {2,3,3},
            {3,1,7},
            {3,4,1},
            {4,1,5},
            {4,3,12}
    };
    static int n= 4; // 表示有4个城市
    static int map2[][] = new int[n][n];

    public static void main(String[] args) {
        //初始化二阶矩阵
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                if(j!=k){
                    map2[j][k] = 9999;
                }
            }
        }
        //给二阶矩阵赋值
        for(int[] x:map){
            map2[x[0]-1][x[1]-1] = x[2];
        }
        //Floyd_WarShall
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                for(int m=0;m<n;m++){
                    if(map2[k][m]>map2[k][j]+map2[j][m]){
                        map2[k][m] = map2[k][j]+map2[j][m];
                    }
                }
            }
            print();
        }
    }

    public static void print(){
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                System.out.print(map2[j][k]+"\t");
            }
            System.out.println();
        }
        System.out.println();
    }
}
